#include "StdAfx.h"
#include "NeighborEnumerator.h"
#include "ContourDot.h"
#include "Stroke.h"

NeighborEnumerator::NeighborEnumerator(float inMaxX, float inMaxY, 
	float inDistanceCriterion, int inCapacity)
	:	mWidth(int(inMaxX / inDistanceCriterion)),
		mHeight(int(inMaxY / inDistanceCriterion)),
		mDistanceCriterion(inDistanceCriterion),
		mDistanceCriterionSquared(inDistanceCriterion * inDistanceCriterion)
{
	mListHeads = (int*)::calloc(mWidth * mHeight, sizeof(int));
	mNodes = (Node*)::malloc(inCapacity * sizeof(Node));
	mFreeNodeIndex = inCapacity;
}


NeighborEnumerator::~NeighborEnumerator()
{
	::free(mListHeads);
	::free(mNodes);
}

void NeighborEnumerator::Add(const ContourDot& inDot, const Stroke* inStroke, int inStrokeEnd)
{
	if (0 >= mFreeNodeIndex)
	{
		// do not add beyond the capacity
		return;
	}
	int cellX, cellY;
	GetCoordinates(&inDot, cellX, cellY);

	int* indexPtr = &mListHeads[cellX + mWidth * cellY];
	while (int i = *indexPtr)
	{
		indexPtr = &mNodes[i - 1].nextIndex;
	}
	*indexPtr = mFreeNodeIndex;
	Node& newNode = mNodes[--mFreeNodeIndex];
	newNode.nextIndex = 0;
	newNode.isSelfVisited = false;
	newNode.info.dot = &inDot;
	newNode.info.stroke = inStroke;
	newNode.info.strokeEnd = inStrokeEnd;
}

bool NeighborEnumerator::SelectNeighbors(const ContourDot& inDot, 
	bool inAvoidRepeatingPairs)
{
	int cellX, cellY;
	GetCoordinates(&inDot, cellX, cellY);

	// we select cells in the matrix 3x3 around the central cell (or smaller at the borders)
	int minX = max(0, cellX - 1);
	int maxX = min(mWidth - 1, cellX + 1);
	int minY = max(0, cellY - 1);
	int maxY = min(mHeight - 1, cellY + 1);

	int i = 0;
	for (int x = minX; x <= maxX; ++x)
	{
		for (int y = minY; y <= maxY; ++y)
		{
			if (int listHead = mListHeads[x + mWidth * y])
			{
				mCurrentIndexSelection[i++] = listHead;
			}
		}
	}
	mCurrentSelection = i;
	mCurrentIndex = 0;
	mAvoidRepeatingPairs = inAvoidRepeatingPairs;
	mCurrentDot = &inDot;
	return (0 < i);
}

const NeighborEnumerator::Info* NeighborEnumerator::FindNextNeighbor()
{
	Info* result = NULL;
	int i = mCurrentIndex;
	while (0 <= mCurrentSelection)
	{
		if (0 == i)
		{
			--mCurrentSelection;
			if (0 > mCurrentSelection)
			{
				break;
			}
			i = mCurrentIndexSelection[mCurrentSelection];
		}
		
		Node& node = mNodes[i - 1];
		i = node.nextIndex;

		if (mAvoidRepeatingPairs && node.isSelfVisited)
		{
			continue;
		}
		if (node.info.dot == mCurrentDot)
		{
			node.isSelfVisited = true;
			continue;
		}
		// check proximity
		const ContourDot* dot = node.info.dot;
		float dx = dot->GetX() - mCurrentDot->GetX();
		float dy = dot->GetY() - mCurrentDot->GetY();
		if (dx * dx + dy * dy < mDistanceCriterionSquared)
		{
			result = &node.info;
			mCurrentIndex = i;
			break;
		}
	}
	
	return result;
}

const NeighborEnumerator::Info* NeighborEnumerator::GetInfoForStrokeEnd(
	const Stroke* inStroke, int inStrokeEnd) const
{
	if (const ContourDot* dot = inStroke->GetContourDotAt(inStrokeEnd))
	{
		int cellX, cellY;
		GetCoordinates(inStroke->GetContourDotAt(inStrokeEnd), cellX, cellY);

		for (int i = mListHeads[cellX + mWidth * cellY]; 0 < i;)
		{
			const Node& node = mNodes[i-1];
			if (node.info.dot == dot && inStrokeEnd == node.info.strokeEnd
				&& inStroke == node.info.stroke)
			{
				return &node.info;
			}
			i = node.nextIndex;
		}
	}
	return NULL;
}

float NeighborEnumerator::GetDistanceCriterion() const
{
	return mDistanceCriterion;
}

void NeighborEnumerator::GetCoordinates(const ContourDot* inDot, 
	int& outX, int& outY) const
{
	int cellX = int(inDot->GetX() / mDistanceCriterion);
	int cellY = int(inDot->GetY() / mDistanceCriterion);

	// clip to the ranges (0... mWidth-1), (0... mHeight-1)
	outX = max(0, min(cellX, mWidth - 1));
	outY = max(0, min(cellY, mHeight - 1));
}